package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2020/1/4
 */
public class FindTilt {

    public static void main(String[] args) {
        System.out.println(findTilt(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.right = new TreeNode(3);
        ret.left.left = new TreeNode(4);
        ret.right.left = new TreeNode(5);
        return ret;
    }

    private static int sum;

    public static int findTilt(TreeNode root) {
        sum(root);
        return sum;
    }

    private static int sum(TreeNode root) {
        if ( root != null ) {
            int l = sum(root.left);
            int r = sum(root.right);
            sum += Math.abs(l - r);
            return l + r + root.val;
        }
        return 0;
    }

    private static int val(TreeNode node) {
        return node == null ? 0 : node.val;
    }

}
